
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <math.h>

#include "ss.h"

SS_counter *is_monitored(SS_type *, int);
void increment_counter(SS_type *, SS_counter *);
void SS_printall(SS_type *);

SS_type * SS_Init(float epsilon)
{
	int i;
	int numc = (int)ceil(1.0/epsilon);
	//printf("\nSS: counters=%d", numc);
	
	SS_type *result = (SS_type *)calloc(1, sizeof(SS_type));
	if (result == NULL) { printf("\ncalloc error");	exit(100); }
	
	result->bfirst = (SS_bucket *)calloc(1, sizeof(SS_bucket));
	if (result->bfirst == NULL) { printf("\ncalloc error");	exit(100); }
	result->bfirst->value = 0;
	result->bfirst->next = NULL;
	result->bfirst->prev = NULL;
	result->N = 0;
	result->numc = numc;
	result->numb = 1;

	/* create the counters */
	SS_counter *ctr = (SS_counter *)calloc(1, sizeof(SS_counter));
	if (ctr == NULL) { printf("\ncalloc error"); exit(100);	}
	ctr->id = 0;
	ctr->prev = NULL;
	ctr->bucket = result->bfirst;

	SS_counter *firstctr = ctr;
	SS_counter *node;

	for (i=1; i<numc; i++) {
		node = (SS_counter *)calloc(1, sizeof(SS_counter));
		if (node == NULL) { printf("\ncalloc error"); exit(100); }
		node->id = i;
		node->eps = 0;
		node->bucket = result->bfirst;
		node->next = NULL;
		node->prev = ctr;
		ctr->next = node;
		ctr=node;
	}
	
	result->bfirst->ctr = firstctr;

	return(result);
}

void SS_printctrs(SS_bucket *b)
{
	SS_counter *c;

	for (c=b->ctr; c != NULL; c = c->next) {
		printf("\n%ld, %ld", c->id, c->eps);
	}

}

SS_counter *is_monitored(SS_type *ss, int item)
{
	SS_bucket *b;
	SS_counter *c;
	
	for (b=ss->bfirst; b != NULL; b = b->next) {
		for (c=b->ctr; c != NULL; c = c->next) {
			if (c->id == item) {
				//printf("\nFound %d", item);
				return(c);
			}
		}
	}

	return(NULL);
}

void SS_Update(SS_type *ss, int item, int ttype)
{
	SS_counter *c = is_monitored(ss, item);
	SS_counter *em;

	ss->N++;

	if (c == NULL) {	// the replacement step
		em = ss->bfirst->ctr;
		em->id = item;
		em->eps = ss->bfirst->value;
		increment_counter(ss, em);
	} else {
		increment_counter(ss, c);
	}
}

void increment_counter(SS_type *ss, SS_counter *c)
{
	SS_bucket *b, *bplus, *newb;
	b = c->bucket;
	long cnt = b->value;
	cnt++;
	
	// detach c
	if (c->prev != NULL) {	// c is not first counter for a bucket
		c->prev->next = c->next;	
		if (c->next != NULL) {
			c->next->prev = c->prev;
		}
	} else {		// c is first counter for a bucket
		c->bucket->ctr = c->next;
		if (c->next != NULL) {
			c->next->prev = NULL;
		}
	}
	c->next = NULL;
	c->prev = NULL;
		
	bplus = b->next;
	if (bplus == NULL || bplus->value != cnt) {	// bplus needs to be created
		ss->numb++;
		newb = (SS_bucket *)calloc(1, sizeof(SS_bucket));
		if (newb == NULL) { printf("\ncalloc error"); exit(100); }
		newb->value = cnt;
		newb->ctr = c;
		newb->prev = c->bucket;
		newb->next = c->bucket->next;
		newb->prev->next = newb;
		if (newb->next != NULL)
			newb->next->prev = newb;
		newb->ctr->bucket = newb;
	} else {	// bplus exists
		c->next = bplus->ctr;
		bplus->ctr->prev = c;
		c->prev = NULL;
		bplus->ctr = c;
		c->bucket = bplus;
	}

	if (b->ctr == NULL) {	// bucket b is empty
		ss->numb--;
		if (b->prev != NULL) {
			b->prev->next = b->next;
			if (b->next != NULL) {
				b->next->prev = b->prev;
			}
		} else {	// b is first bucket
			ss->bfirst = b->next;
			if (b->next != NULL) {
				b->next->prev = NULL;
			}
		}

		free(b);
	}
}

void SS_printall(SS_type *ss)
{
	SS_bucket *b;
	SS_counter *c;
	
	for (b=ss->bfirst; b != NULL; b = b->next) {
		printf("\nBucket->value: %d ", b->value);
		if (b->prev != NULL) printf("L: %d ", b->prev->value); else printf("L: NULL ");
		if (b->next != NULL) printf("R: %d ", b->next->value); else printf("R: NULL ");
		printf("\n");
		for (c=b->ctr; c != NULL; c = c->next) {
			printf("(%d,%d) ", c->id, c->eps);
		}
	}
	printf("\n------");
}

void SS_Destroy(SS_type *ss)
{
	SS_bucket *b, *btemp;
	SS_counter *c, *ctemp;

	for (b=ss->bfirst; b->next != NULL; b = b->next)
		;
		
	do {
		for (c=b->ctr; c->next != NULL; c = c->next)
			;

		do {
			ctemp = c->prev;
			free(c);
			c = ctemp;
		} while (ctemp);
		
		btemp = b->prev;
		free(b);
		b = btemp;
	
	} while (btemp);

	free(ss);
}


unsigned int *SS_Output(SS_type *ss, int th)
{
	unsigned int *list;
    int res = 0;		// counter for no. of freq. items 

    list = calloc(ss->N / th, sizeof(unsigned int));
    if (list == NULL) {	printf("\nCalloc error. ");	exit(400); }

	SS_bucket *b;
	SS_counter *c;
	
	//printf("Freq. elements: \n");
	for (b=ss->bfirst; b != NULL; b = b->next) {
		if (b->value < th) {
			continue;
		}
		for (c=b->ctr; c != NULL; c = c->next) {
			res++;
			list[res] = c->id;
			//printf("%d ", list[res]);
		}
	}

	list[0] = res;	// no. of freq. items found
	
	return(list);
}

int SS_Size(SS_type *ss)
{
	return(ss->numb * sizeof(SS_bucket) + ss->numc * sizeof(SS_counter) + sizeof(SS_type));
}


#ifdef TEST
int main()
{
	int i;
	
	SS_type *ss = SS_Init(20);

	for (i=0; i<5; i++) {
		SS_Update(ss, 10, 1);
		SS_Update(ss, 15, 1);
	}
	
	for (i=0; i<10; i++) {
		SS_Update(ss, 11, 1);
		SS_Update(ss, 16, 1);
	}
	
	SS_Update(ss, 41, 1);
	SS_Update(ss, 51, 1);
	
	for (i=0; i<30; i++) {
    	SS_Update(ss, i, 1);
	}
	
	for (i=0; i<30; i++) {
    	SS_Update(ss, i, 1);
	}
	for (i=0; i<100; i++) {
    	SS_Update(ss, i, 1);
	}
	
	SS_printall(ss);

	unsigned int *list;

	list = SS_Output(ss, 20);

	SS_Destroy(ss);
}
#endif

